package 题目集.图.链式前向星;

public class 链式前向星模板 {
    static int maxN = 100010;
    static int maxM = 200010;
    static int[] h=new int[maxN]; // 表示每个点的第最后一条边的编号
    static int[] pre =new int[maxM];    // 表示每条边的上一条边的编号（存储依赖关系）
    static int[] t=new int[maxM];    // 表示每条边的终点（实际存储边的数组）
    static int[] w=new int[maxM];    // 表示每条边的权值
    static int cnt=1; // 表示当前边的编号
    public static void main(String[] args) {
        int[][] edge={{1,3,1},{1,2,3},{2,1,2},{2,4,7},{3,5,6},{4,5,9},{5,1,8}};
        int n=5;
        for (int[] ints : edge) {
            int from=ints[0];
            int to=ints[1];
            int weight=ints[2];
            t[cnt]=to;  // 表示当前边的终点
            w[cnt]=weight;   // 表示当前边的权值
            pre[cnt]=h[from];    // 表示当前边的上一条边的编号
            h[from]=cnt++;      // 表示当前边的编号
        }

        for (int i = 1; i <= n; i++) {
            child(i);
        }

    }
    public static void child(int x){
        System.out.print(x+".child:\t");
        for (int i = h[x]; i != 0; i = pre[i]) {
            int y = t[i];
            int weight = w[i];
            System.out.print(y+"(w="+weight+")\t");
        }
        System.out.println();
    }
}
